1. Technical Field
The present invention relates, in general, to an improved method and system to be utilized with wireless communication systems having cellular architectures. In particular, the present invention relates to an improved method and system, to be utilized with wireless communication systems having cellular architectures, and which assign groups of channels to individual cells within the system in such a fashion that system-wide channel interference is minimized over some defined geographical area.
2. Description of the Related Art
The present invention is related to wireless communication systems, and, in particular, to wireless communication systems having a cellular architecture (e.g., cellular telephony, Personal Communication Systems, or Global System for Mobil Communication). Wireless communication refers to the fact that transmission between sending and receiving stations occurs via electromagnetic radiation not guided by any hard physical path (e.g., by microwave link.) Cellular architecture refers to the fact that the wireless system effects service over an area by utilizing a system that can be pictographically represented as a cellular grid.
Wireless cellular communication is the latest incarnation of a technology that was originally known as mobile telephone systems. Early mobile telephone system architecture was structured similar to television broadcasting. That is, one very powerful transmitter located at the highest spot in an area would broadcast in a very large radius. If a user were in the useable radius, then that user could broadcast to the base station and communicate by radiotelephone to the base station. However, such systems proved to be very expensive for the users and not very profitable to the communication companies supplying such services. The primary limiting factor of the original mobile telephone systems was that the number of channels available for use was limited due to severe channel-to-channel interference within the area served by the powerful transmitter. Thus, a problem arose as to how to provide more channels within the service area.
Counterintuitively, engineers discovered that channel-to-channel interference effects within the service area were not due solely to the distance between stations communicating with the base transmitter (which intuitively would seem to give rise to the interference), but were also inversely related to the transmitter power (radius) of the area being served by the transmitter. Engineers found that by reducing the radius of an area by fifty percent, service providers could increase the number of potential customers in an area fourfold. It was found that systems based on areas one-kilometer in radius would have one hundred times more channels than systems based on areas ten-kilometers in radius. Speculation led to the conclusion that by reducing the radius of areas to a few hundred meters, the number of calls that could be served by each cell could be greatly increased.
Thus, reducing the power of the central transmitter allowed a significant increase in the number of available channels by reducing channel-to-channel interference within an area. However, as the power of the central transmitter was reduced, the serviceable area was also reduced. Thus, although reducing transmission power increased the number of available channels, the small service area provided by such reduced power did not make such radio telephone systems attractive communication options for many users. Thus, a problem arose relating to how to utilize the discovery that smaller cell sizes increased available channels in a fashion that would provide service attractive to users.
This problem was solved by the invention of the wireless cellular architecture concept. The wireless cellular architecture concept utilizes geographical subunits called "cells" and is buttressed by what is known as a frequency reuse concept. A cell is the basic geographic unit of a cellular system. Cells are base stations (a base station consists of hardware located at the defining location of a cell and includes power sources, interface equipment, radio frequency transmitters and receivers, and antenna systems) transmitting over small geographic areas that are represented as hexagons. Each cell size varies depending on the landscape. The term "cellular" comes from the honeycomb shape of the areas into which a coverage region is divided. Because of constraints imposed by natural terrain and man-made structures, the true shape of cells is not a perfect hexagon, but such shape serves as an effective tool for design engineering.
Within each cell a base station controller talks to many mobile subscriber units at once, utilizing one defined transmit/receive communications channel per mobile subscriber unit. A mobile subscriber unit (a control unit and a transceiver that transmits and receives wireless transmissions to and from a cell site) uses a separate, temporary wireless channel to talk to a cell site. Transmit/receive communication channels utilize a pair of frequencies for communication--one for transmitting from the cell site base station controller, named the forward link, and one frequency for the cell site to receive calls from the users, named the reverse link. Both the forward and reverse link must have sufficient bandwidth to allow transmission of user data.
The frequency reuse concept is what made wireless cellular communications a viable reality. Wireless communication is regulated by government bodies (e.g., the Federal Communications Commission.) Government bodies dictate what frequencies in the wireless spectrum can be utilized for particular applications. Consequently, there is a finite set of frequencies available for use with cellular communications. The frequency reuse concept is based on assigning to each cell a group of radio channels used within a small geographic area (cell). Adjacent cells are assigned a group of channels that is completely different from any neighboring cell. Thus, in the frequency reuse concept there are always buffer cells between two cells utilizing the same set of frequencies. The cells are sized such that it is not likely that two cells utilizing the same set of frequencies will interfere with each other. Thus, such a scheme allows "frequency reuse" by non-adjacent cells.
Since each contiguous cell utilizes different frequencies, the ability for such a system to supply continuous service across a cell grid requires that a call-in-progress be switched to a new transmit/receive channel as a user transits from one cell into another. That is, since adjacent areas do not use the same wireless channels, a call must either be dropped or transferred from one wireless channel to another when a user crosses the line between adjacent cells. Because dropping the call is unacceptable, the process of "handoff" was created. Handoff occurs when the mobile telephone network automatically transfers a call from wireless channel to wireless channel as a mobile subscriber unit crosses adjacent cells.
Handoff works as follows. During a call, a moving mobile subscriber unit is utilizing one voice channel. When the mobile unit moves out of the coverage area of a given cell site, the reception becomes weak. At this point, the base station controller in use requests a handoff. The system switches the call to another different frequency channel in a new cell without interrupting the call or alerting the user. The call continues as long as the user is talking, and generally the user barely notices the handoff.
The foregoing ideas of cells, frequency reuse, and handoff constituted the invention of the cellular concept. The invention of the cellular concept made the idea of wireless cellular communications a viable commercial reality.
As noted previously, the frequency reuse concept requires assigning groups of cells different groups of frequencies. In practice, in order to do the assignment engineers first assume an ideal hexagon layout of the network and apply an ideal frequency assignment pattern "as if" the distribution of the electromagnetic energy being transmitted to achieve communication perfectly matches the hexagonal shapes.
The frequency assignment method is typically done on some variation of a graph coloring approach. Those skilled in the art will recognize that graph coloring recognizes that with at least three different colors a graph can be colored such that each no two contiguous graph shapes have the same color. Accordingly, under the graph coloring approach, the assignment problem is formulated as a graph coloring problem where different channels will be grouped into at least three groups, and the at least three groups are thereafter assigned colors. Thereafter, each hexagon is colored such that no hexagons of the same color are directly adjacent, which is a way to assure that no two cells adjacent cells will be utilizing the same group of channels. In addition, there have been attempts to train neural networks to mimic what human engineers do by experience and intuition.
FIGS. 1A, 1B, and 1C illustrate how the frequency assignment problem is typically solved. In FIG. 1A there is depicted a cell cluster within a wireless communication system having a cellular architecture. Recall that in the above discussion it was noted that frequency reuse is a concept that has been utilized to allow cellular communications over a large area. It is common to create a cell cluster composed of idealized hexagonal cells, as is shown in FIG. 1A, whereby the frequency reuse concept is implemented. A cell cluster is a group of cells. Typically, no channels are reused within a cluster. FIG. 1A illustrates seven-cell cluster 100.
A "cell" is the basic geographic unit of a cellular system. The term "cellular" comes from the honeycomb shape of the areas into which a coverage region is divided. In FIG. 1A each cell 101, 102, 103, 104, 105, 106, and 107 is depicted as a honeycomb shape within which base stations 111, 112, 113, 114, 115, 116 and 117, respectively, are shown. Cells are pictographic representations of the effective geographic area of base station (a base station includes but is not limited to transmitters and receivers sufficient to service existing cell channels within a particular cell) transmitters that are for convenience represented as hexagons. Each cell size varies depending on the landscape. Because of constraints imposed by natural terrain and man-made structures, the true shape of cells is not a perfect hexagon.
Since seven-cell cluster 100 utilizes the frequency reuse concept, each cell in FIG. 1A utilizes a set of channels wherein each channel is based upon a set of carrier frequencies different from those utilized by any other cell 101, 102, 103, 104, 105, 106, 107 within 7-cell cluster 100 (an example of how this can be actually achieved is set forth in FIGS. 1B and 1C, below). Thus, if available frequencies are divided evenly, each cell 101, 102, 103, 104, 105, 106, and 107 will utilize 1/7 of frequencies available for utilization.
When available frequencies are reused across 7-cell cluster 100, it is said that the system has a frequency reuse factor of N=7. As an aid to engineering, frequency reuse tables have been constructed to help communications engineers map the appropriate frequencies into the appropriate cells in as efficient a manner possible under the state of the art.
An example of such a frequency reuse table appears in FIG. 1B.
FIG. 1B depicts an exemplary frequency-reuse table for a system where N=7 (e.g., the frequencies are being re-used across a 7-cell cluster). In a standard system, it is common to have 21 carrier frequency groups available. The frequency reuse table is constructed by creating a first row containing 21 available carrier frequencies. Thereafter, subsequent rows are constructed such that each column in the table has 21 channel frequency separation from the other channels in the column. For example, in the second row it is shown that the 22nd carrier-frequency-in-sequence channel is assigned into channel group 1; thereafter, the same general scheme is followed until all available carriers are so assigned.
Subsequent to constructing the frequency table of FIG. 1A, each 7 contiguous channel groups are assigned onto 7-cell clusters, such as 7-cell cluster 100. To do this, each cell is first divided into three "sectors" x, y, and z. FIG. 1C illustrates a three sector cell representation of a 7-cell cluster. Shown is that each cell in the 7-cell cluster 150 is divided into three sectors x, y, and z. Consequently, shown in FIG. 1C are sectors x.sub.1-7, y.sub.1-7, z.sub.1-7.
With respect to the tri-sector cells of FIG. 1C and the frequency reuse table of FIG. 1B, it is typical to assign channel group 1-7 to sectors x.sub.1-7, channel groups 8-14 to a sectors y.sub.1-7, and channel groups 15-21 to sectors z.sub.1-7. Thereafter, such mapping is repeated over the geographic area such that no sectors with the same subscripts are adjacent.
Inspection of the assignment of frequency groups as shown in FIGS. 1B-1C shows that such assignments make sure that no directly-adjacent carrier frequencies are extant in adjacent sectors. That is, the N=7 scheme in conjunction with the 21 group frequency reuse table insures that buffer zones exist between sectors such that adjacent sectors do not have directly-adjacent carrier frequencies. Consequently, such a system is "balanced" in that it insures that a buffer sector is always available between sectors utilizing the same or directly-adjacent frequencies. It has been found empirically that such assignment gives the best overall system signal-to-noise ratios under the state of the art.
Relatively recently, increasing user bandwidth requirements have prompted communications engineers to attempt to construct frequency reuse schemes which increase bandwidth. One such scheme is an N=6frequency reuse concept. In an N=6 frequency reuse concept, the available frequencies are reused across 6 cells rather than 7. Since such a scheme no longer provides for the perfect buffer zones, or no longer provides the "balance" demonstrated via FIGS. 1B and 1C, the system wide signal-to-noise ratio is generally worse than that for an N=7 system. However, by a trial and error approach communications engineers are generally able to achieve an increase in bandwidth such that from a cost-benefit analysis standpoint the decrease in signal-to-noise ratio is acceptable given the increased bandwidth yielded by such N=6 schemes.
The electromagnetic energy very rarely matches the perfectly arranged hexagonal shapes shown. Variations in terrain and buildings often disrupt the transmitted electromagnetic energy. Consequently, after such an N=6 scheme has been laid out and groups of frequencies assigned, it is generally found that the frequency assignments are grossly inadequate. Thus, subsequent to the N=6 assignment, it is typical that a long period of "trial and error" is engaged in where engineers actually go out and empirically determine the true distribution of the individual cells (which often is radically different in shape than the idealized hexagon). Then, after the shape has been adequately determined, the engineers measure the interference in the cells utilizing different channel group assignments and subsequently assign groups of channels based upon the empirical data.
While a similar labor-intensive process is engaged in for the N=7 schemes, those skilled in the art will recognize that much more labor intenisivity is generally required for the N=6 schemes, due the fact that the N=6 schemes have less buffer zones to start with, which gives rise to numerous directly-adjacent channels between directly adjacent sectors.
It is undeniable that the increased bandwidth of N=6 schemes is very desirable. However, as has been discussed, the ultimate deployment of such systems is difficult due to their unbalanced nature.
It is therefore apparent that a need exists for a method and system which allow an increase in bandwidth over and above that of currently available relatively balanced systems, including but not limited to the N=7 scheme, and yet substantially decrease or eliminate the costs, such as directly-adjacent channels, decreased signal-to-noise ratios, and increased difficulty in depolyablitiy, ordinarily associated with such an increase in bandwidth over and above that of currently available relatively balanced systems.